#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#define maxn 1000
using namespace std;
int t, m, dp[10000005], w[10005], v[10000005];
int main()
{
    ios::sync_with_stdio(false);
    cin >> t >> m;
    for (int i = 1; i <= m; ++i)
        cin >> w[i] >> v[i];
    for (int i = 1; i <= m; ++i)
        for (int j = w[i]; j <= t; ++j)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    cout << dp[t] << endl;
    return 0;
};